#include <stdio.h>
#include <stdlib.h>


typedef struct List {
    // 顺序表的实现（利用数组）
    int * arr;
    // 数组容量
    int capacity;
    // 当前存储元素个数
    int size;
} * ArrayList;

/**
 * 初始化顺序表
 * @param list 顺序表
 */
_Bool initList(ArrayList list) {
    // 动态分配内存空间
    list->arr = malloc(sizeof(int) * 5);
    // 初始化失败
    if(list->arr == NULL) {
        return 0;
    }
    list->capacity = 5;
    list->size = 0;
    // 成功
    return 1;
}

/**
 * 顺序表插入操作
 * @param list
 * @param index 位序，插入第几个位置
 */
_Bool insertList(ArrayList list, int index, int data) {
    // index非法，插入失败
    if(index < 1 || index > list->size + 1) {
        return 0;
    }
    // 扩容
    if(list->size == list->capacity) {
        // 原来容量的1.5倍
        int newCapacity = list->capacity + (list->capacity >> 1);
        // 使用函数realloc()扩大内存
        int * newArr = realloc(list->arr, sizeof(int) * newCapacity);
        list->arr = newArr;
        list->capacity = newCapacity;
    }
    for (int i = list->size; i > index - 1; i--) {
        // 从插入位置开始所有元素向后移动
        list->arr[i] = list->arr[i-1];
    }
    // 插入元素
    list->arr[index - 1] = data;
    // 记录元素个数
    list->size++;
    return 1;
}

/**
 * 顺序表删除操作
 * @param list
 * @param index 位序，从1开始
 * @return
 */
_Bool deleteList(ArrayList list, int index) {
    //非法删除
    if(index < 1 || index > list->size) {
        return 0;
    }
    // 从删除位置开始，后面的往前移动
    for (int i = index - 1; i < list->size; ++i) {
        list->arr[i] = list->arr[i+1];
    }
    // 长度减小
    list->size--;
    return 1;
}

/**
 * 通过位序查找元素
 * @param list
 * @param index 位序，从1开始
 * @return 返回查找的元素
 */
int getDataByIndex(ArrayList list, int index) {
    // 非法位序
    if(index < 1 || index > list->size) {
        return INT_MAX;
    }
    int data = list->arr[index - 1];
    return data;
}

/**
 * 顺序表当前长度
 * @param list
 * @return 返回长度大小
 */
int getListLength(ArrayList list) {
    return list->size;
}

/**
 * 打印数据
 * @param list
 */
void printList(ArrayList list) {
    for (int i = 0; i < list->size; ++i) {
        printf("%d", list->arr[i]);
        printf("\t");
    }
}


int main1() {
    // 创建新的结构体变量（为什么不可以直接ArrayList list呢？）
    struct List list;
    printf("开始初始化\n");
    if(initList(&list)) {
        insertList(&list, 1, 20);
        insertList(&list, 1, 30);
        insertList(&list, 1, 50);
        insertList(&list, 1, 60);
        insertList(&list, 1, 70);
        insertList(&list, 1, 80);
        deleteList(&list, 6);
        printList(&list);
        printf("当前长度：%d\n", getListLength(&list));
        printf("当前查找元素为：%d", getDataByIndex(&list, 1));
    } else {
        printf("初始化失败");
    }
}


